package utils

/* 有序双向链表 */

const (
	desc = 1
	asc  = 0
)

type Node[K comparable, V any] struct {
	Key      K
	Value    V
	next     *Node[K, V]
	previous *Node[K, V]
}

type SortedLinkedList[K comparable, V any] struct {
	head        *Node[K, V]
	compareFunc func(a K, b K) int // a>b -> 1 ; a==b -> 0; a<b -> -1
	mutex       rwMutex            // 可控是否加锁
	order       int                // 排序（默认 ASC 1 2 3）
	length      int                // 数据长度
	//repeatFunc  func(key K, value V) bool // 判断节点是否重复的方法（true=>重复）
}

func NewSortedLinkedList[K comparable, V any](cf func(a K, b K) int) *SortedLinkedList[K, V] {
	res := &SortedLinkedList[K, V]{
		compareFunc: cf,
		mutex:       rwCreate(), // 默认没有开启锁
		order:       asc,
	}
	return res
}

func (ll *SortedLinkedList[K, V]) WithLock(b ...bool) {
	ll.mutex = rwCreate(b...)
}

func (ll *SortedLinkedList[K, V]) OrderByDesc() {
	ll.order = desc
}

func (ll *SortedLinkedList[K, V]) Insert(key K, value V) {
	newNode := &Node[K, V]{Key: key, Value: value}
	fc := ll.compareFunc
	ll.mutex.Lock()
	defer ll.mutex.Unlock()

	if ll.head == nil {
		ll.head = newNode
		ll.length++
		return
	}

	// 如果链表为空或插入节点的值小于头节点的值，则将新节点作为新的头节点
	/* 头插 */
	/* 小于等于head.key && 使用ASC排序(false)   => true */
	/* 大于head.key && 使用DESC排序(true)    => true */
	/* 小于等于head.key && 使用DESC排序(true)   => false */
	/* 大于head.key && 使用ASC排序(false)    => false */

	if (fc(key, ll.head.Key) <= 0 && ll.order == asc) || (ll.order == desc && fc(key, ll.head.Key) >= 0) {
		/* ASC:输入 小于 头节点 ；DESC:输入 大于 头结点  */
		ll.head.previous = newNode
		newNode.next = ll.head
		ll.head = newNode
		ll.length++
		return
	}

	prev := ll.head
	curr := ll.head.next
	for curr != nil && ((fc(key, curr.Key) >= 0 && ll.order == asc) || (fc(key, curr.Key) <= 0 && ll.order == desc)) {
		/* 找到： ASC: 输入 大于 current节点 ；DESC:输入 小于 头结点  */
		prev = curr
		curr = curr.next
	}

	prev.next = newNode
	newNode.previous = prev
	newNode.next = curr
	if curr != nil {
		curr.previous = newNode
	}
	ll.length++
}

// 作为头部插入，头节点
func (ll *SortedLinkedList[K, V]) insertInHead(newNode *Node[K, V]) {
	if ll.head == nil {
		ll.head = newNode
		ll.length++
		return
	}
	ll.head.previous = newNode
	newNode.next = ll.head
	ll.head = newNode
	ll.length++
}

// 作为中间节点或者尾节点插入
func (ll *SortedLinkedList[K, V]) insertInLink(preNode, curr, newNode *Node[K, V]) {
	preNode.next = newNode
	newNode.previous = preNode
	newNode.next = curr
	if curr != nil {
		curr.previous = newNode
	}
	ll.length++
}

func (ll *SortedLinkedList[K, V]) Range(f func(*Node[K, V]) bool) {
	ll.mutex.Lock()
	defer ll.mutex.Unlock()
	curr := ll.head
	for curr != nil {
		if !f(curr) {
			break
		}
		curr = curr.next
	}
	return
}

func (ll *SortedLinkedList[K, V]) Len() int {
	ll.mutex.RLock()
	num := ll.length
	ll.mutex.RUnlock()
	return num
}

func (ll *SortedLinkedList[K, V]) DeleteOne(f func(*Node[K, V]) bool) {
	ll.delete(f, 1)
}

func (ll *SortedLinkedList[K, V]) DeleteAll(f func(*Node[K, V]) bool) {
	ll.delete(f, -1)
}

// 删除满足条件的当前节点与后续所有节点
func (ll *SortedLinkedList[K, V]) DeleteAfter(f func(*Node[K, V]) bool) {
	ll.mutex.Lock()
	defer ll.mutex.Unlock()
	curr := ll.head
	length := 0
	for curr != nil {
		if f(curr) {
			pre := curr.previous
			if pre != nil {
				pre.next = nil
			} else {
				// 证明是删除了header节点
				ll.head = curr.next
			}
			curr.previous = nil
			ll.length = length
			return
		}
		length++
		curr = curr.next
	}
}

func (ll *SortedLinkedList[K, V]) delete(f func(*Node[K, V]) bool, num int) {
	ll.mutex.Lock()
	defer ll.mutex.Unlock()
	curr := ll.head
	for curr != nil {
		if f(curr) {
			num--
			pre := curr.previous
			after := curr.next

			if pre != nil {
				pre.next = curr.next
			} else {
				// 证明是删除了header节点
				ll.head = after
			}

			if after != nil {
				after.previous = pre
			}

			curr.previous = nil
			curr.next = nil
			ll.length--
			if num == 0 {
				break
			}

			curr = after
		} else {
			curr = curr.next
		}
	}
}

// //////////////////////////////////////////////////////////////////////
